The present invention relates to computer implementations of simultaneous auctions of multiple items, wherein combinatorial bidding is permitted. More particularly, the present invention involves the use of bid composition restrictions to pace such auctions and to eliminate certain damaging strategic manipulations that have been used by bidders in such auctions.
Since 1994, when the U.S. Federal Communications Commission (FCC) adopted the simultaneous ascending auction. (xe2x80x9cSAAxe2x80x9d, also known as the xe2x80x9csimultaneous multiple round auction,xe2x80x9d as its primary auction method, more than $20 billion of radio spectrum has been sold using this method. Initial public reaction to the spectrum auctions was enthusiastic. A 1995 New York Times article describing the FCC""s auction of spectrum for personal communications services carried the headline: xe2x80x9cThe Greatest Auction in History.xe2x80x9d A balanced review by the Congressional Budget Office gave the whole series of FCC auctions high marks for both novelty and successful outcomes.
Although the SAA incorporates significant new elements, some of its rules resemble those of the well-known xe2x80x9csilent auctionsxe2x80x9d commonly used in charity sales. In silent auctions, tables are filled with the multiple lots to be sold (or pictures or descriptions of the items), and bidders write their bids in a list on a page beside each lot.
Like the silent auction, the SAA is a simultaneous sale of multiple items in which bidding closes for all the items at the same time: However, the SAA differs from the silent auctions in several ways. First, at least in the variant used by the FCC, SAA bids are submitted in a series of discrete rounds rather than continuously in time. Second, the SAA typically employs a computerized interface that makes it practical to run the auction remotely (for example, by a dial-in system or over the Internet), which in turn makes its practical to extend the auction over a long period of time. When an electronic implementation is used, it also enables bidders to keep track of bidding on many related items in a simple manner. Third and most important, the SAA incorporates some rules that are distinctly different from the silent auction. Among these are the closing rule that keeps bidding open for all items until there is a sufficient period with no new bidding for any item, the activity rule that prevents a bidder from refraining from active bidding until near the end of the auction, and the bid increment rule that controls the pace of the auction by determining appropriate minimum bid increments.
The FCC has conducted simultaneous ascending auctions for as few as ten or as many as 2,000 spectrum licenses. Although most SAAs conducted to date have been spectrum sales, SAAs have been run successfully in several countries for a wide variety of assets and contract obligations, including undeveloped real estate, mining rights, and standard offer electrical service obligations.
To fully appreciate the contribution of the present invention, it is important to understand: a) economic auction theory, b) the mechanics of combinatorial auctions, and c) prior art bid restrictions, i.e., additive activity rules.
A. Efficiency as the Objective of Auction Designs
In a seller""s auction, an allocation of goods is economically xe2x80x9cefficientxe2x80x9d if the overall valuexe2x80x94consisting of the price received by the seller plus the net value received by the winning biddersxe2x80x94is as large as possible. (Buyer""s auctions have an analogous standard.) Economic efficiency is a fundamental objective of both public and private sector auction sales and overall value is a key criterion for evaluating auction performance.
When governments sell assets, economic efficiency is often listed as an objective of the auction. In the U.S. spectrum auctions, federal legislation specified that xe2x80x9cefficient use of the electromagnetic spectrumxe2x80x9d was the primary objective of the allocation process. The FCC""s initial auction order explicitly interpreted this legislative objective to mean economically efficient use. Similarly, the sales of SO2 pollution permits and airport landing rights also have economic efficiency as a primary objective.
In most private sector auctions and in some public sector auctions, the seller instead specifies maximizing revenues as the main objective of the sale. However, maximizing revenues requires attracting potential bidders to participate and compete, which in turn requires holding out the possibility of significant profits for the winning bidder. According to the economics literature, the connection between participation and the winner""s potential profits is so strong that it sometimes makes the problem of revenue maximization identical to the problem of overall value maximization. In practice, this justifies the rule of thumb that more efficient designs lead to higher auction revenues in seller""s auctions.
B. Classical Auction Theory
The idea that concurrent bidding for multiple goods helps to find market-clearing prices and their associated efficient allocations has a long history in economic thought, dating back to the 19th Century. At that time, economists recognized that the demand for one good would generally depend on the prices of other goods. For example, the quantity of wheat demanded at a given price would generally depend on the prices of other grains and perhaps also on the prices of other foods, as well as on the cost of milling services, transportation, storage, and so on.
Although early economic thinkers understood that market-clearing prices of different goods could not be found individually without reference to one another, they offered no practical means to discover and set such prices. The Walrasian auction, which was central to economic theories about price setting, is a dynamic process in which the price of each good may increase or decrease at different times during the auction. The non-monotonic behavior of prices in the Walrasian auction can interfere with the convergence of the process, as published examples in the economics literature have shown. Even when convergence does theoretically occur, it can be very slow because some prices will rise and fall many times before approaching their final values. Finally, the convergence or the speed of convergence of the Walrasian auction process is not something that is guaranteed. Rather, it is a prediction based on assumptions about the participants"" behaviorxe2x80x94assumptions that are contrary to the incentives of the participants and which are thus unlikely to be satisfied in reality. Consequently, although classical economic analysis was useful in identifying weaknesses in non-simultaneous price setting, it ultimately had little to contribute to the implementation of real auctions for multiple goods.
C. Recent Auction Theory
Recent scholarly research does contain ideas that are useful for designing and implementing real auctions for multiple goods. For example, it has recently been shown that a simultaneous ascending auction leads to market-clearing prices and supports economically efficient allocations if the goods offered for sale are mutual substitutes and the bidders always bid straightforwardly for the goods they want. [Two goods are xe2x80x9csubstitutesxe2x80x9d if raising the price of one increases (or at least never reduces) demand for the other; goods are mutual substitutes if each good is a substitute for every other good in the set. For example, apples and pears are substitutes. If the price of apples were to rise significantly, some consumers would buy pears instead, thereby increasing the total demand for pears. Similarly, apples, pears, and bananas are xe2x80x9cmutual substitutes.xe2x80x9d A bidder bids xe2x80x9cstraightforwardlyxe2x80x9d in a round when he bids as if he were the sole remaining active bidder, with all other bidders expected to make no more bids.]
The SAA also has the very desirable property that no price can ever decrease during the course of the auction. This monotonicity of prices in the SAA guarantees that the auction process will eventually end, regardless of the bidding strategies adopted by the bidders, so long as bidders limit themselves to bids they are capable of fulfilling. This guarantee is necessary for any practical auction mechanism.
The preceding observations help to explain the apparent successes of SAAs in contexts where all the goods are substitutes. However, theory has also shown that auctions that set prices individually for discrete, indivisible goods (e.g., a SAA) cannot lead to economically efficient outcomes if some of the goods are complements for some bidders, but substitutes for other bidders. (Two goods are xe2x80x9ccomplementsxe2x80x9d if raising the price of one reduces demand for the other. For example, hotel rooms and airline seats are complements: an increase in the price of airline tickets tends to reduce the demand for hotel rooms by reducing the amount of consumer travel.) Indeed, the very idea that efficiency can be achieved by setting individual prices for goods fails in these circumstances because, as the theory shows, it may not be possible to balance supply and demand in all markets using prices. In such cases, pricing bundles of products, such as vacation packages that include hotel and airfare, may be necessary to clear the market.
The case of goods that can be complements for some bidders and substitutes for other bidders is of enormous practical importance. For example, in a radio spectrum auction, a license to use a band of radio spectrum in one particular area is of little practical value if the area is too small or the bandwidth too narrow. So, for some bidders, two small chunks of nearly identical spectrum may be complementary parts of a larger package. For other bidders who already own large amounts of bandwidth to which they wish to add a single chunk, the same two chunks of spectrum are likely to be substitutes.
When goods can be complements for some bidders and substitutes for others, the bidders for whom the goods are complements face an exposure problem. The exposure problem in the SAA is that a bidder must risk becoming the high bidder on at least one good in a set of complements before it knows what it will have to pay to acquire the other goods in the set. For example, consider a bidder that wishes to purchase two related goods, A and B, but only if the bidder can acquire both. At some point in the SAA, this bidder must make a high bid on A or B individually, without knowing what it might eventually cost to acquire the other good. The bidder risks the possibility that his bid for A will win while the price of B rises too high to make B""s acquisition worthwhile. Overall, this can result in a loss for the bidder because A alone is not valuable to the bidder.
One consequence of the exposure problem is that bidders become reluctant to bid. This is bad for two reasons: it tends to reduce the revenue enjoyed by the seller from the auction and it may result in a loss of overall value, as goods wind up in the hands of someone who does not actually value them the most. Another consequence is that bidders may aim to gain an artificial advantage by creating an exposure problem for a competitor. If they succeed, these manipulations lead to further losses of both revenue and overall value.
In practice, parties that conduct auctions sometimes consult with bidders in advance of the auction and try to create xe2x80x9clotsxe2x80x9d consisting of the packages that likely high bidders will want. For example, in the FCC auctions for personal communication services (PCS) spectrum, after extensive public consultations, the lots sold included some licenses for 30 MHz of radio spectrum bandwidth (to support new entrants into PCS services) and licenses for 10 MHz of bandwidth (to enlarge existing spectrum packages).
Any decision about how to structure the lots is both technically complex and a critical determinant of the success of the auction. An example of the consequences of poorly structured lots can be found in an auction conducted by the Netherlands spectrum management agency in February 1998. This auction was for radio spectrum allocated for use in the next generation of cellular telephones. The spectrum was divided into 18 lots. Two of these were efficiently sized for a new entrant to establish service. The remaining 16 lots were small and intended to be available either to supplement existing licenses or to be combined for use by a new entrant. The outcome had three notable features. First, both large lots were acquired by new entrants to the wireless telephone business. Second, the smaller lots were acquired mostly by incumbents, that is, firms that already licensed some spectrum and offered wireless telephone services. Finally, the prices per unit of spectrum for each of the small lots were less than half of the corresponding price per unit of spectrum for the two larger lots. The low prices for the small lots are explained by examining the round-by-round behavior of bidders in the auction. New entrants that lost the bidding for the larger lots dropped out of the auction without even attempting to combine the relatively cheap small lots into large blocks, which is precisely the behavior one would expect from bidders faced with an exposure problem. The result was low prices for the poorly structured lots and a loss of overall value.
Decisions about how to structure lots in government-run auctions are politically charged because the lot packaging affects the likely auction outcome. Such decisions can also affect whether bidders choose to-participate at all.
For example, in the proceedings to structure the FCC spectrum auctions for personal communication services, MCI lobbied strongly to have a nationwide license included in the auction. For regulatory reasons, MCI was the only major U.S. telephone company eligible to bid on a nationwide license, so the creation of such a license would likely have allowed it to acquire spectrum cheaply. Conversely, without such a license offering, MCI would have faced an exposure problem, because it would risk acquiring licenses without enough geographical coverage to enable it to establish a nationwide wireless telephone system. When MCI""s proposal was rejected, it decided not to participate in the auction at all.
Even an auctioneer with the best of intentions often has too little independent information to structure the lots effectively. The auctioneer must rely to some degree on the calculated representations by potential bidders. Because bidders may use these representations strategically to distort the outcome in their favor, the current politicized process of auctioneers defining lots has serious drawbacks.
In view of the difficulties that arise when the seller (or the buyer in a buyer""s auction, i.e., the entity on whose behalf the auction is being held) tries to package items into lots, the best chance for efficient outcomes is often to employ an auction method that allows bidders to make xe2x80x9ccombinatorial bidsxe2x80x9d that specify the combinations they desire as well as the prices they are willing to pay. In the FCC application, the bids would specify combinations of geography and bandwidth. Combinatorial bids completely protect bidders from the exposure problem because they never force bidders to buy individual lots that they do not want.
The use of combinatorial bidding for major assets has well-established precedents. For example, bankruptcy trustees auctioning a bankrupt firm""s, assets sometimes accept bids both for the whole firm and for the individual assets, accepting the set of bids that yield the largest total price. In several recent sales in the U.S. of electrical generating assets in connection with the deregulation of electric utilities, the investment bankers running the auctions allowed bids for individual assets as well as for combinations of assets. In each of these auctions, the combinatorial bids were static, once-and-for-all bids. They could not be revised based on new information that might have emerged during the course of the auction.
A. Static Combinatorial Bidding: Theory
The theory of combinatorial bidding has a distinguished history. In the work most emphasized in his Nobel Prize citation, laureate William Vickrey introduced a version of it to economic theory. An extension of Vickrey""s method (sometimes called the xe2x80x9cgeneralized Vickrey auctionxe2x80x9d) calls upon bidders to specify values for all possible combinations of items and determines prices based on those reported values. According to the theory, if bidders (i) had unlimited budgets, (ii) were certain about their estimates of value, and (iii) found it costless to estimate values for every one of the many combinations that might be sold, then this system would lead to outcomes that maximize the overall value created by the auction. However, because an auction for N items entails 2N combinations, an auction for as few as twenty items involves more than one million combinations. Thus, even for such a modestly sized application, specifying values for all combinations becomes completely impractical, violating Vickrey""s third condition.
Even if the scale difficulty can sometimes be overcome, the generalized Vickrey auction has still more shortcomings and limitations. One shortcoming is that, under Vickrey""s pricing rules, two bidders who purchase identical items may be asked to pay different prices. This characteristic xe2x80x9cprice discriminationxe2x80x9d that is built into the Vickrey auction raises a fatal objection for many government-run auctions, in which perceived fairness is commonly a paramount criterion. The same objection is also significant in privately run auctions, because the auctioneer may worry that such rules impair its ability to attract bidders.
Another class of objections to the generalized Vickrey auction is that one of the other two enumerated conditions in Vickrey""s analysis fails to hold, so his conclusions do not apply. Indeed, real bidders are rarely certain about their valuations and may spend significant sums to improve their estimates and assessments in a large auction, violating Vickrey""s second condition. Also, most bidders have limited budgets and thus need to limit their bid totals to what they can afford, violating Vickrey""s first condition. When any one of the enumerated conditions fails, the outcome of the generalized Vickrey auction is not guaranteed to maximize total value. Even when the conditions are met, the auction is not guaranteed to maximize seller revenues. For each of these reasons, it can be better to implement a dynamic combinatorial bidding system in which bidders use the information inferred from competing bids to decide which combinations to bid on and how much to bid.
B. Dynamic Combinatorial Bidding: Theory
A xe2x80x9cdynamic combinatorial auctionxe2x80x9d is an auction with the following features. First, bids may be made for individual lots or limited combinations of lots. Thus, a bid consists of a pair (S, b) where S is the set of lots covered and b is the money amount bid for that set. Second, the auction engine evaluates the entire set of bids submitted by all the bidders to select a set of tentative xe2x80x9cwinningxe2x80x9d bids. The winning set is chosen from among the qualifying sets, which are sets of bids in which each lot is awarded only once. [This means that if (S1, b1) and (S2, b2) are any two bids in a qualifying set, then the two sets do not contain any common lots, i.e., the intersection of S1 and S2 is the empty setxe2x80x94S1∩S2=Ø.] Among the qualifying sets, in a seller""s auction, the tentative winning set is one that maximizes the total bid price. (Conversely, in a buyer""s auction, the tentative winning set is the one that minimizes the total bid price.) Third, bidders receive sufficient feedback about the bids that have already been made to enable them to determine which new bids would win if no other new bids were made. Also, unlike the Vickrey auction, dynamic combinatorial auctions are usually constructed so that the price a bidder pays for a lot or combination is equal to the amount it bid.
There are many possible variations of dynamic combinatorial auctions. The auctions may be conducted in a series of discrete rounds or they may allow new bids to be submitted and evaluated at any time during the auction, or there may be a hybrid of these two schemes. Complete details about the bids received and who made them may be communicated to all the bidders immediately or with delay, or some details may be withheld entirely. A bid that is displaced from the winning set may disappear from the system immediately or be held in reserve, or it may remain in reserve unless withdrawn by the bidder. (With combinatorial bidding, a bid""s status as part of the winning bid package may depend on other bids, so a bid that is displaced and held in reserve may later become part of a new winning package.)
Dynamic combinatorial bidding has at least three major advantages over its static counterpart. First, bidders do not need to specify bids for every combination of lots at the outset of the bidding. As discussed above, such lists of bids can be unreasonably long even in relatively small auctions. Second, the information that emerges during the auction can help the bidders both to select the combinations of lots on which they wish to bid and to avoid the winner""s curse, i.e., the tendency of the winning bidder to be a party whose estimate of the value of the lots for sale is too high. Third, it may ease the problem of bidders who face significant budget restrictions and whose bids for some items depend not only on which other items they acquire but also on the amounts to be paid for those items.
While there is some practical experience with dynamic combinatorial auctions, most of the relevant experience comes from economics laboratory experiments. Interest in these auctions has increased because recent federal legislation requires the FCC to investigate the feasibility of combinatorial bidding for its spectrum auctions. A version of this auction that was proposed to the FCC is called the xe2x80x9csimultaneous ascending auction with package biddingxe2x80x9d (SAAPB).
A serious disadvantage of existing dynamic combinatorial auctions, including the SAAPB, is that they create strategic opportunities for xe2x80x9clargexe2x80x9d bidders to disadvantage smaller competitors. The problem is that current dynamic combinatorial auctions allow a bidder that does not find the items to be complements to increase his chance of winning or of obtaining a relatively low price by bidding as if the items were complements.
Tables 1 and 2 below illustrate this problem. In Table 1, there are three bidders and two lots. Only Bidder 3 is interested in both lots, but suppose Bidder 3 enjoys no actual synergies from owning both: his payoff from acquiring both is just the sum of the payoffs from acquiring each separately. In this example, the absence of synergies means that there is no exposure problem for combinatorial bidding to remedy. Another feature of the example in Table 1 is that Bidder 3""s value for each lot is lower than the value assigned by one of the xe2x80x9csmallerxe2x80x9d bidders, i.e., bidders who are interested in fewer lots than Bidder 3.
If Bidder 3 were forced to bid in open auctions on the individual lots, he would very likely lose the bidding for each lot. The outcome would then be efficient, creating the maximum overall value (of 50+55=105). Suppose, however, that Bidder 3 can make a combinatorial bid of, say, 60 for a package consisting of lots A and B in an open, ascending auction. Bidders 1 and 2 are then forced to play a game of xe2x80x9cchickenxe2x80x9d with each other. After Bidder 3""s bid of 60, Bidder 1 would prefer to wait for Bidder 2 to raise his bid for Lot B so that Bidder 1 can acquire Lot A cheaply. Bidder 2 has the reverse interests. Each may wait for the other to blink. The outcome of this contest is uncertain (using economics terminology, some Nash equilibria involve mixed strategies), but the inefficient outcome in which Bidder 3 wins the lots (and the overall value is only 40+40=80) is more likely in this combinatorial auction than in the SAA, in which the lots are sold individually.
Table 2 illustrates another example. This time lot B should be allocated to Bidder 3 in an efficient allocation (because 40 greater than 35). Once again, a bid of 60 by Bidder 3 creates a game of chicken, but this time Bidder 2 has little to gain by helping Bidder 1 to overcome the problem. If Bidder 2 knows this, the coordination problem may prove intractable.
In both examples, Bidder 3 has nothing to lose by bidding for combinations before bidding for the individual lots. If Bidders 1 and 2 manage to coordinate well enough to beat the combinatorial bid, Bidder 3 can simply switch from bidding on the combination {AB} to bidding just on the individual lots A and B and do as well as if he had never made a combinatorial bid.
The lesson of these two examples is clear. Dynamic combinatorial bidding makes efficient outcomes less likely in environments without value synergies. In practice, when the auction is being designed, the designer rarely knows much about the actual extent of the value synergies. With the present combinatorial auctions, the designer is left to guess about whether benefits of combinatorial bidding outweigh the damage inflicted by the manipulative use of combinatorial bids. Consequently, even when the potential benefits of combinatorial bidding are very substantial, the designer may choose to forego them. For instance, when a seller or its agent (e.g., an auctioneer) designs a seller""s auction without knowing all of the value synergies present for the various potential bidders, he may forego having an auction with combinatorial bidding, even when a combinatorial, design is warranted. (Similarly, a buyer or its agent designing a buyer""s auction faces analogous difficulties.) Thus, the strategic opportunities for xe2x80x9clargexe2x80x9d bidders to disadvantage smaller competitors is a major limitation to the general application of current dynamic combinatorial auction designs.
C. Summary Propositions about Combinatorial Bidding
There are four main propositions about combinatorial bidding that are relevant to the present invention. First, when some goods may be complements for some bidders, combinatorial bidding is a necessary feature of any ascending price-setting system that increases prices for goods in excess demand and achieves efficient outcomes. Second, if goods are discrete and may be complements for some bidders and substitutes for others, then there is no system of individual pricing of lots that can support efficient outcomes: combinatorial pricing is necessary. Third, static combinatorial bidding methods, such as the generalized Vickrey auction, can be acceptable and effective only under a set of highly restrictive conditions that severely limits their practical use. Finally, present implementations of dynamic combinatorial bidding create a strategic opportunity for bidders to bid for xe2x80x9clargexe2x80x9d packages to improve their own chances of winning lots that interferes with the achievement of economically efficient outcomes.
A number of attempts have been made to improve the efficiency of simultaneous ascending auctions (with or without package bidding) by introducing additive dynamic restrictions called xe2x80x9cactivity rulesxe2x80x9d that make a bidder""s eligibility for current bidding dependent upon its past bidding activity.
The first such restriction was the so-called xe2x80x9cMilgrom-Wilson activity rule,xe2x80x9d which was adopted by the FCC in 1994 as part of its preferred auction method. Activity rules provide that a bidder may not increase its overall bidding activity late in the auction, that is, a bidder who fails to participate sufficiently at some round of the auction has reduced bidding eligibility at all later rounds of the auction. There are several important practical problems to be resolved in implementing such rules, including identifying appropriate measures of activity and specifying activity requirements that are restrictive enough to promote a rapid pace of the auction but not so restrictive as to disallow legitimate bidding strategies. Several improvements have been made in both of these dimensions since the first SAAs. In every case, however, the activity rule has remained xe2x80x9cadditive,xe2x80x9d i.e., the activity of a bidder is measured by the sum of the activity credits associated with each individual lot. For additive activity rules, a bidder""s later bids are not restricted by the composition of his previous bids, i.e., additive activity rules do not impose any xe2x80x9cbid composition restrictionsxe2x80x9d on a bidder.
Recently, Stanford Professor Robert Wilson has suggested an activity rule for the California Power Exchange (PX) daily power auction. The PX auction is a dynamic two-sided xe2x80x9cDutchxe2x80x9d auction, in which bidders name prices and quantities and improve their bids and offers over time. Wilson""s rule specifies that a bidder who fails in any round to improve a bid or offer that has not resulted in a tentative trade may not later improve that offer. Like the Milgrom-Wilson rule, this rule forces bidders who wish to be active late in the auction to be active continuously throughout the auction. Although the Power Exchange initially accepted Wilson""s suggestion, plans to implement any dynamic Dutch auction have since been scrapped. Wilson""s rule is also additivexe2x80x94it just measures activity by the amount of electrical power specified in qualifying bids.
Some recent scholarly research has focused on finding additive activity rules for dynamic combinatorial auctions. On the one hand, such rules are thought to be important because the computational problem of searching for the total-price maximizing set of combinatorial bids is very hard (i.e., in mathematical terms, it is an xe2x80x9cNP-completexe2x80x9d problem) so that initial rounds of low bidding activity may be particularly damaging. On the other hand, the construction of such rules involves subtle issues that do not arise in simple (non-combinatorial) auctions.
In simple (seller""s) auctions, a bid advances the auction when it displaces the existing high bid for a lot. In a combinatorial (seller""s) auction, bids are not evaluated individually. Indeed, a tentative non-winning bid may become part of a winning set later in the auction. This consideration makes the construction of a useful activity rule much more difficult in combinatorial auctions.
A team of researchers at the University of Arizona and Caltech (DeMartini, Kwasnica, Ledyard and Porter, 1999) has recently suggested an activity rule that attempts to deal with this problem heuristically. In their experimental tests, their rule appears to improve the performance of their dynamic combinatorial auction. However, the Arizona-Caltech rule is yet another additive activity rule that does nothing to reduce a bidder""s strategic incentive to bid for a larger than optimal package.
In the prior art, the bid restrictions that apply during an auction are additive activity rules that measure a bidder""s activity by summing the activity weights of the lots covered by bids. For additive activity rules, it is the coverage of the bidder""s whole collection of bidsxe2x80x94rather than the composition of the individual bidsxe2x80x94that determines future bidding eligibility. Because such rules do not distinguish between different collections of bids covering the same lots, they can never mitigate the problematic strategic incentive for combinatorial bidding.
All of the foregoing shows that there is a need to develop combinatorial auction methods and systems that eliminate the problem of bidding for complements, without also creating the strong adverse incentives that produce inefficient auction outcomes.
The present invention is a new class of dynamic combinatorial auctions that produces more efficient outcomes than prior combinatorial auctions through the use of xe2x80x9cbid composition restrictions.xe2x80x9d The xe2x80x9ccompositionxe2x80x9d of a combinatorial bid is the set of lots that the bid covers. For this new class of auctions, to be recorded a bid""s composition must satisfy one or more restrictions that depend explicitly or implicitly on the bidder""s past history of bidding, i.e., a bidder""s prior bid compositions restrict his later bid compositions. In sharp contrast to previous combinatorial auctions with additive activity rule restrictions, this new class of auctions rewards bidders who bid for the smallest relevant combinations at any point during the auction by offering them additional bidding flexibility later in the auction. At the same time, this new class of auctions does not disadvantage bidders who want to bid on large combinations solely to avoid the exposure problem.
In a preferred embodiment, a computer system connects a plurality of auction participants in an auction for a plurality of items. The auction participants typically include a plurality of bidders and either an entity on whose behalf the auction is conducted or the entity""s agent. The entity is a seller in a seller""s auction, whereas the entity is a buyer in a buyer""s auction. For either a buyer""s auction or a seller""s auction, the entity""s agent may be an auctioneer.
The computer system receives bids from a plurality of bidders. Each bid received includes a grouping of one or more items from the plurality of items and a price.
The computer system applies one or more bid composition restrictions to each bid received. Three exemplary types of bid composition restrictions, which may be applied either singly or in combination, are non-additive activity restrictions, subset restrictions, and superset restrictions. The combination of non-additive activity restrictions and superset restrictions can be particularly effective.
The computer system records only those bids that satisfy the applicable bid composition restrictions (and possibly other types of bid restrictions as well). At the end of the auction, a set of bids is selected from the recorded bids. The selection is preferably done by the computer system, but can also be done by a human. For a seller""s auction, the selected set of recorded bids will typically maximize a value index, such as the total price received for the plurality of items. For a buyer""s auction, the set of recorded bids that either minimizes a cost index, such as the total cost paid for the items being auctioned, or maximizes an index of buyer satisfaction will typically be selected. The selected set of recorded bids is communicated to at least some of the auction participants, such as the seller in a seller""s auction, the buyer in a buyer""s auction, and possibly the bidders as well.